/*
 * @lc app=leetcode.cn id=1489 lang=javascript
 *
 * [1489] 找到最小生成树里的关键边和伪关键边
 */

// @lc code=start
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[][]}
 */
var findCriticalAndPseudoCriticalEdges = function (n, edges) {
  // 建立边与数组下标的索引，方便后面处理结果
  const map = new Map();
  edges.forEach((edge, idx) => {
    map.set(edge, idx);
  });
  edges.sort((a, b) => a[2] - b[2]);

  // 最小生成树并计算权值和
  let value = 0;
  const uf = new UnionFind(n);
  for (const [x, y, weight] of edges) {
    if (uf.union(x, y)) {
      value += weight;
    }
  }

  const result = [[], []];
  const size = edges.length;
  for (let i = 0; i < size; i++) {
    // 判断关键边
    let uf = new UnionFind(n);
    let v = 0;
    for (let j = 0; j < size; j++) {
      const [x, y, weight] = edges[j];
      // 删除一条边并统计最小权值和
      if (j !== i && uf.union(x, y)) {
        v += weight;
      }
    }
    if (uf.count !== 1 || (uf.count === 1 && v > value)) {
      // 图不连通或者权值和大于最小生成树的权值和
      result[0].push(map.get(edges[i]));
      // 关键边也符合伪装关键边性质，所以先判断关键边跳出循环
      continue;
    }

    // 判断伪关键边
    const [x, y, weight] = edges[i];
    uf = new UnionFind(n);
    uf.union(x, y);
    v = weight;
    for (let j = 0; j < size; j++) {
      const [x, y, weight] = edges[j];
      // 从i边开始，找到最小生成树，并统计最小权值和
      if (j !== i && uf.union(x, y)) {
        v += weight;
      }
    }
    if (v === value) {
      // 权值和相同，伪关键边
      result[1].push(map.get(edges[i]));
    }
  }

  return result;
};

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, idx) => idx);
    this.size = new Array(n).fill(1);
    this.count = n;
  }
  find(x) {
    if (x !== this.parent[x]) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  union(x, y) {
    let [ux, uy] = [this.find(x), this.find(y)];
    if (ux === uy) {
      return false;
    }
    if (this.size[ux] < this.size[uy]) {
      [ux, uy] = [uy, ux];
    }
    this.parent[ux] = uy;
    this.size[uy] += this.size[ux];
    this.count--;
    return true;
  }
}
// @lc code=end
